#include <cstring>
#include <iterator>
#include <algorithm>
#include <iostream>
using namespace std;

//n: length of array
//m: positions to be rotated
//TIME = O(2*n);SPACE = O(1)

//beautiful and simple
inline void reverse(int a[],int n)
{
  int *i,*j;
  int tmp;

  for(i=a,j=a+n-1;i<j;i++,j--){
    tmp = *i;
    *i = *j;
    *j = tmp;
  }
  return;
}

void rotate_left(int a[],int n, int m)
{
  m = m%n;
  reverse(a,m);
  reverse(a+m,n-m);
  reverse(a,n);
  return;
}
//left m == right n-m
void rotate_right(int a[],int n, int m)
{
  m = m%n;
  //m <--> n-m
  reverse(a,n-m);
  reverse(a+n-m,m);
  reverse(a,n);
  return;
}

int main()
{
  int a[] = {0,1,2,3,4,5,6,7,8,9};
  copy(a,a+10,ostream_iterator<int>(cout," "));
  cout<<endl;
  rotate_left(a,10,3);
  copy(a,a+10,ostream_iterator<int>(cout," "));
  cout<<endl;
  rotate_right(a,10,3);
  copy(a,a+10,ostream_iterator<int>(cout," "));
  cout<<endl;
  return 0;
}
